
import sun.reflect.generics.tree.Tree;

import java.util.Scanner;
import java.util.*;

public class TestBinaryTree {
    static class TreeNode {
        public char val;
        public int val2;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
        public TreeNode(int val2){
            this.val2=val2;
        }

    }

    TreeNode root;//根节点
    //创建二叉树
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        TreeNode J=new TreeNode('J');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        F.left=J;
        this.root=A;
        return A;
    }
    //前序遍历,根，左,右 ABDEHCFG
    public void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val);//打印根节点
        preOrder(root.left);//传入左子树，打印左子树的根节点
        preOrder(root.right);//传入右子树


    }
    //非递归实现前序遍历创建二叉树
    public void preorderTraversal3(TreeNode root){
        if (root==null){
            return ;
        }
        TreeNode cur=root;
        Deque<TreeNode> stack=new ArrayDeque<>();
        while (cur!=null||!stack.isEmpty()) {

            while (cur != null) {//添加节点
                stack.push(cur);//入栈
                System.out.println(cur.val + " ");
                cur = cur.left;
            }
            //cur为空不进入以上循环，进入以下代码
            TreeNode top=stack.pop();//弹出栈顶元素
            cur=top.right;
        }
    }
    //中序遍历，左,根,右 DBEHAFCG
    public void inOrder(TreeNode root){
        if (root==null){
                return ;
            }
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }
    //非递归中序遍历
    public void inorderTraversal(TreeNode root) {
        if (root==null) {
            return;
        }
        Deque<TreeNode> deque=new ArrayDeque<>();
        TreeNode cur=root;
        while (cur!=null||!deque.isEmpty()){//注意为"|"
            while (cur!=null){
                deque.push(cur);//入栈
                cur=cur.left;//进入左子树
            }
            //cur为空
            TreeNode tmp=deque.pop();//获取栈顶节点
            System.out.println(tmp.val);
            cur=tmp.right;
        }
    }

        //后续遍历，左,右,根 DHEBFGCA
    public void postOrder(TreeNode root){
        if (root==null){
                return;
            }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }
    //非递归打印
    public List<Integer> postorderTraversal(TreeNode root){
        List<Integer> ret=new ArrayList<>();
        if (root==null) {
            return ret;
        }
        Deque<TreeNode> deque=new ArrayDeque<>();
        TreeNode cur=root;
        TreeNode prev = null;//记录是否被打印过
        while (cur!=null||!deque.isEmpty()){//注意为"|"
            //cur不为空进入该循环
            while (cur!=null){
                deque.push(cur);//入栈
                cur=cur.left;//进入左子树
            }
            //cur为空
            TreeNode tmp=deque.peek();//获取栈顶节点
            if (tmp.right==null||tmp.right==prev){
                System.out.println(tmp.val);//后续打印
                deque.pop();
                prev=tmp;
            }else {
                cur=tmp.right;
            }
        }
        return ret;
    }
    List<Integer> ret=new ArrayList<>();
    //递归前序打印
    public List<Integer> preorderTraversal1(TreeNode root) {//遇到一个节点，ret传入一个节点的val
        if (root==null){
            return ret;
        }
        ret.add((int) root.val);
        System.out.print(root.val);//打印根节点
        preorderTraversal1(root.left);//传入左子树，打印左子树的根节点
        preorderTraversal1(root.right);// (root.right);//传入右子树
        return ret;
    }
    public List<Integer> preorderTraversal2(TreeNode root){
        List<Integer> ret=new ArrayList<>();
        func(root,ret);
        return ret;
    }
    public void func(TreeNode root,List ret){
        if (root==null){
            return;
        }
        ret.add(root.val);
        func(root.left,ret);
        func(root.right,ret);
    }
        //子问题思路

    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> ret=new ArrayList<>();
        if (root==null){
            return ret;
        }
        ret.add((int) root.val);
        //产生左子树的ret
        List<Integer> leftTree=preorderTraversal(root.left);
        ret.addAll(leftTree);
            //产生右子树的ret
        List<Integer> rightTree=preorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
        }

    // 获取树中节点的个数

    //子问题思路
    int size(TreeNode root) {//子问题：左树节点+右树节点+1=树节点
        if(root==null){
            return 0;
        }
        int leftlen=size(root.left);
        //count++;

        int rightlen=size(root.right);
        return 1+leftlen+rightlen;
    }
    //遍历思路,遇到一个count+1
    int count=0;
    int size1(TreeNode root) {//子问题：左树节点+右树节点+1=树节点
        if(root==null){
            return 0;
        }
        size1(root.left);
        count++;

        size1(root.right);
        return count;
    }

    // 获取叶子节点的个数
    //子问题思路
    public int getLeafNodeCount(TreeNode root) {
        if (root==null){
            return 0;
        }

        if (root.left==null&&root.right==null){

            return 1;
        }

        int leftlen=getLeafNodeCount(root.left);

        int rightlen=getLeafNodeCount(root.right);
        return leftlen+rightlen;
    }
    // 遍历思路-求叶子结点个数
    int Treesize=0;
    void getLeafNodeCount2(TreeNode root) {
        if (root==null){
            return ;
        }

        if (root.left==null&&root.right==null){
            Treesize++;
        }

        getLeafNodeCount2(root.left);

        getLeafNodeCount2(root.right);

    }

    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root==null){
            return 0;
        }
        if (k==1){//当k减到1时，说明遍历到要求节点的层
            return 1;
        }
        int leftsize=getKLevelNodeCount(root.left,k-1);//根节点在往下走，k层也相对-1
        int rightsize=getKLevelNodeCount(root.right,k-1);
        return leftsize+rightsize;
    }

    // 获取二叉树的高度
    int getHeight(TreeNode root) {
        if (root==null){
            return 0;
        }
        int leftheight=getHeight(root.left);
        int rightheight=getHeight(root.right);

        return (leftheight<rightheight)?(rightheight+1):(leftheight+1);
    }

    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if (root==null){
            return null;
        }
        if (root.val==val){
            return root;
        }

        TreeNode left=find(root.left, val);
        if (left!=null){
            return left;//说明在左子树找到
        }
        //找不到，则一个null代代传承
        TreeNode right=find(root.right, val);
        if (right!=null){
            return right;
        }

        return null;
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        if(root==null){
            return;
        }
        //创建队列
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//入队
        while(!queue.isEmpty()){//当队列不为空
            TreeNode cur=queue.poll();//出队
            System.out.println(cur.val);
            if (cur.left!=null){//左子树不为空
                queue.offer(cur.left);//入队
            }
            if (cur.right!=null){
                queue.offer(cur.right);//入队
            }
        }

    }
    //返回每层的节点值
    public List<List<Character>> levelOrder1(TreeNode root) {
        List<List<Character>> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        //创建队列
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//入队
        while(!queue.isEmpty()){//当队列不为空
            int size= queue.size();;
            List<Character> tmp=new ArrayList<>();
            while(size!=0){
                TreeNode cur=queue.poll();//出队
                System.out.println(cur.val);
                tmp.add(cur.val);
                size--;
                if (cur.left!=null){//左子树不为空
                    queue.offer(cur.left);//入队
                }
                if (cur.right!=null){
                    queue.offer(cur.right);//入队
                }
            }
            list.add(tmp);
        }
        return list;

    }


    //判断两颗树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //根节点都为空 是
        if(p==null&&q==null){
            return true;//两者都为空
        }

        //根节点一空一不为空，不是
        if (p==null&&q!=null||p!=null&q==null){
            return false;
        }

        //根节点不为空--判断左树，判断右树
        //运行到此处为都不是空的情况
        if (p.val!=q.val){
            return false;
        }
        //都不为空且值相等
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root==null||subRoot==null)return false;
        //先判断两个树是否相同
        if(isSameTree(root,subRoot)){
            return true;
        }
        if (isSubtree(root.left,subRoot))return true;
        if (isSubtree(root.right,subRoot))return true;
        return false;
    }
    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //判断平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root==null){//左子树和右子树没有，只有一个节点的情况
            return true;
        }
        int lenH=getHeight(root.left);//获取左子树高度
        int rightH=getHeight(root.right);//获取右子树高度
        return Math.abs(lenH-rightH)<2&&isBalanced(root.left)&&isBalanced(root.right);
        //             绝对值小于2           左子树为平衡二叉树           右子树为平衡二叉树
    }
    //提高效率后的平衡二叉树
    public boolean isBalanced2(TreeNode root) {
        return getHeight(root)>=0;
    }
    int getHeight2(TreeNode root) {
        if (root==null){
            return 0;
        }
        int leftheight=getHeight2(root.left);
        if (leftheight<0)return -1;

        int rightheight=getHeight2(root.right);
        if (rightheight<0)return -1;
        if(Math.abs(leftheight-rightheight)<=1){
            return Math.max(leftheight,rightheight)+1;
        }else{
            return -1;
        }
    }
    //判断是否是对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        return isSymmetricchild(root.left,root.right);

    }
    public boolean isSymmetricchild(TreeNode lefttree,TreeNode righttree){
       if (lefttree==null&&righttree!=null||lefttree!=null&&righttree==null){
           return false;
       }
       if (lefttree==null&&lefttree==righttree){
           return true;
       }
       if (lefttree.val!=righttree.val){
           return false;
       }
       //都不为空且值相等
       return isSymmetricchild(lefttree.left, righttree.right)&&isSymmetricchild(lefttree.right,righttree.left);
    }
    //前序遍历字符串数组并创二叉树
    public  int i=0;
    public  TreeNode createTree(String str){
        TreeNode root=null;
        if (str==null){//字符串为空
            return null;
        }
        if('#' != str.charAt(i)){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else{
            i++;
        }
        return root;
    }



    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root==null){
            return null;
        }
        if (p==root||q==root){
            return root;
        }
        TreeNode lefttree=lowestCommonAncestor(root.left,p,q);
        TreeNode righttree=lowestCommonAncestor(root.right,p,q);
        if (lefttree!=null&&righttree!=null){
            return root;//如果在root的左子树和右子树找到了，说明root为公共祖先
        } else if (lefttree!=null) {//左边找到，右边没找到
            return lefttree;//说明该节点为公共祖先
        } else if (righttree != null) {
            return righttree;
        }
        return null;//说明左右都为空，都找不到
    }
    //查找指定节点并把该路径的节点压入栈
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack){
        if (root==null||node==null){
            return false;
        }
        //根不为空
        stack.push(root);//入栈
        //入栈后检查
        if(root==node){
            return true;
        }
        boolean ret1=getPath(root.left,node,stack);
        if (ret1) {
            return true;//左边找到，一个true不断归
        }

        boolean ret2=getPath(root.right,node,stack);
        if (ret2){
            return true;//右边找
        }
        //走到这里表明ret1和ret2都为false，左边和右边都没找到，该节点无用，出栈
        stack.pop();//栈中出栈左子树和右子树都返回false的根节点，因为证明该节点不是找node的途径节点
        return false;
    }
    //寻找公共祖先
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
        Deque<TreeNode> stack1=new LinkedList<>();
        getPath(root,p, stack1);//途径节点入栈
        Deque<TreeNode> stack2=new LinkedList<>();
        getPath(root,q,stack2);//途径节点入栈
        //
        int size1= stack1.size();;
        int size2= stack2.size();
        if(size1>size2){
            int size=size1-size2;
            while(size!=0){
                stack1.pop();
                size--;
            }
        }else {
            int size=size2-size1;
            while(size!=0){
                stack2.pop();
                size--;
            }
        }
        //stack1和stack2个数相等
        while (!stack1.isEmpty()&&!stack2.isEmpty()){//两者都不为空
            if (stack1.peek()!=stack2.peek()){
                stack1.pop();
                stack2.pop();
            }else
            {
                return stack1.peek();
            }
        }
        return null;
    }
    //根据前序和中序创建二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int sz=inorder.length-1;
        TreeNode root=buildTreeChild(preorder,inorder,0,sz);
        return root;
    }
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbeging,int inend){
        if (inbeging>inend){
            return null;
        }
        //创建根节点
        TreeNode root=new TreeNode(preorder[i]);
        //找中序遍历中i的位置,获取中序遍历中root的下标
        int rootindex=findIndex(inorder,inbeging,inend,preorder[i]);
        i++;
        //创建根左子树
        root.left=buildTreeChild(preorder,inorder,inbeging,rootindex-1);
        //创建根右子树
        root.right=buildTreeChild(preorder,inorder,rootindex+1,inend);
        return root;
    }
    //找到root在中序数组的位置
    private int findIndex(int[] inorder,int inbeging ,int inend,int key){
        for (int j = inbeging; j <=inend; j++) {
            if (inorder[j]==key){
                return j;
            }
        }
        return -1;
    }
    //根据中序和后续创建二叉树
    public int a;
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
         a=postorder.length-1;
        return buildTreeChild2(inorder,postorder,0, postorder.length-1);
    }

    public TreeNode buildTreeChild2(int[] inorder,int []postorder,int pobeging,int poend){
        if (pobeging>poend){
            return null;
        }

        TreeNode root=new TreeNode(postorder[poend]);//从后往前创建根
        int rootindex=findIndex2(inorder,pobeging,poend,postorder[a]);
        a--;
        root.right=buildTreeChild2(inorder,postorder,rootindex+1,poend);//先创建右子树
        root.left=buildTreeChild2(inorder,postorder,pobeging,rootindex-1);
        return root;
    }
    private int findIndex2(int[] inorder,int pobeging,int poend,int key) {
        for (int j = poend; j >= pobeging; j--) {
            if (inorder[j] == key) {
                return j;
            }
        }
        return -1;
    }
    //根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        if (root==null){
            return null;
        }
        StringBuilder stringBuilder=new StringBuilder();//创建字符串
        tree2strchild(root,stringBuilder);//根据二叉树创建字符串

        return stringBuilder.toString();
    }
    //前序遍历创建字符串1(2(4))(3)
    public int j=0;
    public void tree2strchild(TreeNode root,StringBuilder stringBuilder){
        if (root == null){
            return;
        }
        stringBuilder.append(root.val);
        if (root.left!=null){//左子树不为空
            stringBuilder.append("(");
            tree2strchild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {//左边为空
            //根的右子树不为空
            if(root.right!=null){
                stringBuilder.append("()");//添加双括号
                //注意继续向下执行语句
            }else {//根的右子树为空
                return;
            }
        }
        //由于是if语句，无return此处执行完依然会执行下面语句

        if (root.right==null){
            return;
        }else{//上述右子树不为空添加双括号后
            stringBuilder.append("(");
            tree2strchild(root.right,stringBuilder);
            stringBuilder.append(")");
        }

    }
    boolean isCompleteTree(TreeNode root){
        if (root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //队列不为空
            TreeNode cur=queue.poll();
            if (cur!=null){
                queue.offer(root.left);
                queue.offer(root.right);
            }else {//弹出的为空，跳出循环
                break;
            }
        }
        //如果队列不为空，说明上面的循环由Break跳出来的
        while (!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            //检查是否为null
            if (tmp!=null){
                return false;//不是Null，则不是完全二叉树
            }
            //为null继续执行循环
        }
        //循环走完后，队列出来的节点肯定为全null
        return true;
    }
}
